/*
https://www.luogu.com.cn/problem/P1219
作业–八皇后优化：
实际上是枚举𝑛元素排列（每行都可放1 到n，且不重复）
•dfs(row) 枚举第row 行皇后哪列
•验证列、对角线未被占用
用a1[col] 记录第col 列被占用
用a2[row+col] 记录绿对角线被占
a3[13+row-col] 记蓝对角线被占

https://cdn.class.luogu.com.cn/lils/yugu22jcc3/3.svg
*/
#include <bits/stdc++.h>
using namespace std;
int n, outputCnt, solCnt;
int a[20], a1[20], a2[30], a3[30]; //全局数组自动初始化

void dfs(int row) {
    if (row == n + 1) {
        if (outputCnt < 3) {
            for (int i = 1; i <= n; i++)
                cout << a[i] << " ";
            cout << endl;
            outputCnt++;
        }
        solCnt++;
        return;
    }

    for (int col = 1; col <= n; col++) {
        // 考虑第 row 行的皇后放在第 col 列
        if(  !a1[col] 
            && !a2[row + col] 
            && !a3[13 + row - col]) {

            a[row] = col;
            a1[col] = 1;
            a2[row + col] = 1;
            a3[13 + row - col] = 1;
            dfs(row + 1);
            a1[col] = 0;
            a2[row + col] = 0;
            a3[13 + row - col] = 0;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << solCnt << endl;
    return 0;
}

